package com.yx.study.leet.daily;

/**
 * @Classname numPrimeArrangements1175
 * @Date 2022/06/30 21:30
 * @Author by yx
 * @Description :
 */
public class numPrimeArrangements1175 {
    int mod = 1_000_000_007;

    public int numPrimeArrangements(int n) {
        int primeCount = eratosthenes(n);// 素数的个数
        long primeArrange = factorial(primeCount) % mod;// 素数的排列组合
        long noPrimeArrange = factorial(n - primeCount) % mod;//非素数的排列组合
        return (int) ((primeArrange * noPrimeArrange) % mod);
    }

    // 阶乘
    private long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        long tmp = factorial(n - 1);
        tmp %= mod;
        return n * tmp;
    }

    // 埃氏筛选法求素数个数
    private int eratosthenes(int n) {
        //false代表是素数，true代表不是素数
        boolean[] isPrime = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i])// 如果不是素数跳过
            {
                continue;
            }
            count++;// 素数加1，
            // 素数的倍数都不是素数
            for (int j = i + i; j <= n; j += i) {
                isPrime[j] = true;
            }
        }
        return count;
    }
}
